#include <map>
#include <list>

using namespace std;

class Pair
{
  friend class Graph;

private:
  int node;
  int weight;

public:
  Pair(int n, int w);
  friend ostream& operator<< (ostream& out, Pair& p);
  int operator== (const Pair& p) const;
};

class Graph
{
private:
  map<int, list<Pair> > pairMap;
  int numEdges;
  int numNodes;
public:
  Graph();
  void add(int node1, int node2, int weight);
  void remove(int node1,int node2);
  int getNumNodes();
  int edgeCost(int node1, int node2);
  bool isEulerian();
  list<int> getEulerian();
  list<int> getOdds(); 
  void dijkstra(int source);
  void floydWarshall(int** path, int** next);
  static list<int> getPath(int i, int j, int** path, int** next);
  static list<int> getDoubles(int **path,list<int> vetor);
  void duplicateEdges(list<int> pairs,int **path,int **next);
  int DFS(int *visitados,int inicial);
  bool isBridge(int node1,int node2,int tamanho);
  friend ostream& operator<<(ostream& out, Graph& g);
};
